Search results for "adjacent vertex-distinguishing"

showing 2 items of 2 documents

Neighbor-Distinguishing k-tuple Edge-Colorings of Graphs

2009

AbstractThis paper studies proper k-tuple edge-colorings of graphs that distinguish neighboring vertices by their sets of colors. Minimum numbers of colors for such colorings are determined for cycles, complete graphs and complete bipartite graphs. A variation in which the color sets assigned to edges have to form cyclic intervals is also studied and similar results are given.

Circular coloringComputingMethodologies_IMAGEPROCESSINGANDCOMPUTERVISION0102 computer and information sciences[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]01 natural sciencesGraphTheoretical Computer ScienceCombinatoricsGreedy coloringIndifference graphChordal graphDiscrete Mathematics and Combinatorics0101 mathematicsFractional coloringComputingMilieux_MISCELLANEOUSComputingMethodologies_COMPUTERGRAPHICSMathematicsDiscrete mathematicsk-tuple edge-coloringClique-sum010102 general mathematics[ INFO.INFO-DM ] Computer Science [cs]/Discrete Mathematics [cs.DM]1-planar graphMetric dimension010201 computation theory & mathematicsIndependent setMaximal independent setNeighbor-distinguishingMathematicsofComputing_DISCRETEMATHEMATICSAdjacent vertex-distinguishing
researchProduct

Vertex Distinguishing Edge- and Total-Colorings of Cartesian and other Product Graphs

2012

International audience; This paper studies edge- and total-colorings of graphs in which (all or only adjacent) vertices are distinguished by their sets of colors. We provide bounds for the minimum number of colors needed for such colorings for the Cartesian product of graphs along with exact results for generalized hypercubes. We also present general bounds for the direct, strong and lexicographic products.

[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]total coloringadjacent vertex-distinguishingvertex-distinguishingComputingMethodologies_IMAGEPROCESSINGANDCOMPUTERVISIONedge-coloring[ INFO.INFO-DM ] Computer Science [cs]/Discrete Mathematics [cs.DM]graphgraph productsAMS 05C15[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]total adjacent vertex-distinguishingMathematicsofComputing_DISCRETEMATHEMATICS
researchProduct